package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;

/**
 * 找到所有数组中消失的数字
 * <p>给你一个含 n 个整数的数组nums，其中 nums[i]在区间[1, n]内。
 * <p>请你找出所有在[1, n]范围内但没有出现在nums中的数字，并以数组的形式返回结果。
 *
 * @author c2b
 * @since 2022/5/19 17:39
 */
public class LC0448findDisappearedNumbers {

    /**
     * 找到所有数组中消失的数字
     *
     * @param nums 数组
     * @return java.util.List<java.lang.Integer> 所有数组中消失的数字
     * @author c2b
     * @since 2022/5/19 17:41
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // 例如 ： 4,3,2,7,8,2,3,1
        for (int i = 0; i < nums.length; i++) {
            // i =0 ==> nums[nums[0]-1] *(-1)= nums[3] *(-1)  -->7==>-7
            // i =1 ==> nums[nums[1]-1] *(-1)= nums[2] *(-1)  -->2==>-2
            int val = Math.abs(nums[i]) - 1;
            if (nums[val] > 0) {
                nums[val] *= -1;
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                res.add(i + 1);
            }
        }
        return res;
    }

    /**
     * 找到所有数组中消失的数字(这个更优)
     *
     * @param nums 数组
     * @return java.util.List<java.lang.Integer> 所有数组中消失的数字
     * @author c2b
     * @since 2022/5/19 18:13
     */
    public List<Integer> findDisappearedNumbers2(int[] nums) {
        // 数组长度（如果数字出现过,那么该数字对应的数组下表-1位置的值加上数组长度）
        int length = nums.length;
        // 例如 ： 4,3,2,7,8,2,3,1
        for (int i = 0; i < nums.length; i++) {
            // 一个数加上数组长度,再模上数组长度,和修改前结果是一样的
            int val = (nums[i] - 1) % length;
            nums[val] += length;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= length) {
                res.add(i + 1);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] ints = {1, 1};
        for (Integer disappearedNumber : new LC0448findDisappearedNumbers().findDisappearedNumbers2(ints)) {
            System.out.println(disappearedNumber);
        }
    }
}
